Leetcode-Longest Common Prefix

发表于 | 分类于 |

Longest Common Prefix

最长相同前缀：给定一个字符串数组，找出其中最长的共同前缀。这里leetcode并没有说明共同前缀是指两两之间的前缀还是所有字符串的前缀，实际题意是指采用所有字符串的共同前缀。
Description

解题思路：
若字符串数组为空则返回空字符串；
否则从所有字符串中找出最短的字符串，依次将最短字符串的每个元素和所有字符串对应位置上的元素进行比较，若不同则停止比较并返回；
若全部相同，则返回最短字符串。

1
2
3
4
5
6
7
8
9
10
11
if not strs:
    return ""

shortest = min(strs, key=len)

for i in range(len(shortest)):
    for string in strs:
        if shortest[i] != string[i]:
            return shortest[:i]
        
return shortest

改进：
将字符串数组进行排序(注意，这里是按照字母表顺序排序，而不是根据长度排序），排序后实际只要比较第一个和最后一个字符串的共同前缀即可，因此大大提升了运行时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
if not strs:
          return ""
      
      strs.sort()
      first = strs[0]
      last = strs[-1]
      minlen = min(len(first), len(last))
                  
      for i in range(minlen):
          if first[i]!=last[i]:
              return first[:i]
              
      return first[:minlen]